package zuochengyun;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;

//找出出现次数大于K的数
public class MoreThanKTimesNumber {

	//核心思想就是一旦找到K个不同的数之后，就删除掉这些数，那么最后剩下的数就一定是大于K次的
	public void printKMajor(int[] arr, int K){
		if(K < 2){
			System.out.println("the value is invalid");
			return;
		}
		HashMap<Integer, Integer> candidates = new HashMap<>();
		for (int i = 0; i < arr.length; i++) {
			if(candidates.containsKey(arr[i])){
				candidates.put(arr[i], candidates.get(arr[i]) + 1);
			}else{
				//把所有不同的数减1
				if(candidates.size() == K - 1){
					allCandsMinusOne(candidates);
				}else{
					candidates.put(arr[i], 1);
				}
			}
		}
		
		HashMap<Integer, Integer> reals = getReals(arr, candidates);
		//用来判断是否可以打印
		boolean canPrint = false;
		for (Entry<Integer, Integer> set : candidates.entrySet()) {
			Integer key = set.getKey();
			if(reals.get(key) > arr.length / K){
				canPrint = true;
				System.out.println(key + " ");
			}
		}
		System.out.println(canPrint ? "" : "no such number");
	}
	
	/**
	 * 将所有的candidates减1
	 * @param candidates
	 */
	public void allCandsMinusOne(HashMap<Integer, Integer> candidates){
		//记录需要移除的key
		List<Integer> removeList = new LinkedList<>();
		for(Entry<Integer, Integer> set : candidates.entrySet()){
			Integer key = set.getKey();
			Integer value = set.getValue();
			if(value == 1){
				removeList.add(key);
			}
			candidates.put(key, value - 1);
		}
		
		for (Integer removeKey : removeList) {
			candidates.remove(removeKey);
		}
	}
	
	/**
	 * 得到candidates 中记录的最后剩下的数出现的次数，已验证是否出现了K次
	 * @param arr
	 * @param candidates
	 * @return
	 */
	public HashMap<Integer, Integer> getReals(int[] arr, HashMap<Integer, Integer> candidates){
		HashMap<Integer, Integer> reals = new HashMap<>();
		for (int i = 0; i < arr.length; i++) {
			int curNum = arr[i];
			if(candidates.containsKey(curNum)){
				if(reals.containsKey(curNum)){
					reals.put(curNum, reals.get(curNum) + 1);
				}else{
					reals.put(curNum, 1);
				}
			}
		}
		return reals;
	}
}
